#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        int res = 0;
        sort(nums.begin(), nums.end());

        int n = nums.size();
        for (int k = n - 1; k >= 0; k--) { // 固定右边
            int l = 0;
            int r = k - 1;

            while (l < r) {
                int mid = (l + r) / 2;
                if (nums[mid] + nums[k] < target) {
                    l ++;
                } else {
                    r--;
                }
            }
            cout << (l + r) / 2 << endl;
            res += (l + r) / 2;
        }

        return res;
    }
};

// 这段代码想计算数组中 **两数之和小于 `target` 的对数**，但当前实现存在多个问题：

// ---

// ### ❌ 主要问题

// 1. **二分逻辑错误**

//    ```cpp
//    while (l < r) {
//        int mid = (l + r) / 2;
//        if (nums[mid] + nums[k] < target) l++;
//        else r--;
//    }
//    ```

//    这里每次循环只移动 `l++` 或 `r--`，并没有根据 `mid` 调整边界，二分意义丢失，实际上退化成线性扫描，且结果不正确。

// 2. **统计方式错误**
//    `res += (l + r) / 2;` 并不能正确统计满足条件的对数。

// 3. **输出 `(l+r)/2`**
//    打印调试值没有实际意义，也无法验证对数。

// ---

// ### ✅ 正确方法

// 目标：计算 **有多少对 `(i, j)` 满足 `nums[i] + nums[j] < target`**。

// 可以用 **排序 + 双指针**（O(n²)）或者**二分**（O(n log n)）实现。

// #### 双指针方法

// ```cpp
// #include <vector>
// #include <algorithm>
// using namespace std;

// class Solution {
// public:
//     int countPairs(vector<int>& nums, int target) {
//         sort(nums.begin(), nums.end());
//         int res = 0;
//         int n = nums.size();
//         int l = 0, r = n - 1;

//         for (int i = 0; i < n - 1; i++) {
//             int j = i + 1;
//             while (j < n && nums[i] + nums[j] < target) {
//                 j++;
//             }
//             res += (j - i - 1);
//         }
//         return res;
//     }
// };
// ```

// 解释：

// * 外层固定一个数 `nums[i]`；
// * 内层找到第一个 `nums[j]`，使 `nums[i] + nums[j] >= target`，那么 `[i+1, j-1]` 都满足条件；
// * 累加 `(j - i - 1)` 即为有效对数。

// #### 二分方法

// ```cpp
// #include <vector>
// #include <algorithm>
// using namespace std;

// class Solution {
// public:
//     int countPairs(vector<int>& nums, int target) {
//         sort(nums.begin(), nums.end());
//         int res = 0;
//         int n = nums.size();

//         for (int i = 0; i < n - 1; i++) {
//             // 找第一个 >= target - nums[i] 的位置
//             int j = lower_bound(nums.begin() + i + 1, nums.end(), target - nums[i]) - nums.begin();
//             res += (j - i - 1);
//         }

//         return res;
//     }
// };
// ```

// * `lower_bound` 返回第一个大于等于 `target - nums[i]` 的位置，左边的所有元素加上 `nums[i]` 都小于 `target`；
// * 累加 `(j - i - 1)` 即为有效对数。

// 这种方法更接近你的二分思路，同时保证了正确性。
